﻿//------------------------------------------------------------
// Copyright (c) Microsoft Corporation.  All rights reserved.
// System.ServiceModel.Internals\System\Runtime\IOThreadTimer.cs
//------------------------------------------------------------

#if DESKTOPCLR
using System;
using System.ComponentModel;
using System.Security;
using System.Threading;
using Microsoft.Win32.SafeHandles;
using CuteAnt.Runtime.Interop;

namespace CuteAnt.Runtime
{
  // IOThreadTimer has several characterstics that are important for performance:
  // - Timers that expire benefit from being scheduled to run on IO threads using IOThreadScheduler.Schedule.
  // - The timer "waiter" thread thread is only allocated if there are set timers.
  // - The timer waiter thread itself is an IO thread, which allows it to go away if there is no need for it,
  //   and allows it to be reused for other purposes.
  // - After the timer count goes to zero, the timer waiter thread remains active for a bounded amount
  //   of time to wait for additional timers to be set.
  // - Timers are stored in an array-based priority queue to reduce the amount of time spent in updates, and
  //   to always provide O(1) access to the minimum timer (the first one that will expire).
  // - The standard textbook priority queue data structure is extended to allow efficient Delete in addition to 
  //   DeleteMin for efficient handling of canceled timers.
  // - Timers that are typically set, then immediately canceled (such as a retry timer, 
  //   or a flush timer), are tracked separately from more stable timers, to avoid having 
  //   to update the waitable timer in the typical case when a timer is canceled.  Whether 
  //   a timer instance follows this pattern is specified when the timer is constructed.
  // - Extending a timer by a configurable time delta (maxSkew) does not involve updating the
  //   waitable timer, or taking a lock.
  // - Timer instances are relatively cheap.  They share "heavy" resources like the waiter thread and 
  //   waitable timer handle.
  // - Setting or canceling a timer does not typically involve any allocations.

  public class IOThreadTimer
  {
    const int maxSkewInMillisecondsDefault = 100;
    static long systemTimeResolutionTicks = -1;
    Action<object> callback;
    object callbackState;
    long dueTime;

    int index;
    long maxSkew;
    TimerGroup timerGroup;

    public IOThreadTimer(Action<object> callback, object callbackState, bool isTypicallyCanceledShortlyAfterBeingSet)
        : this(callback, callbackState, isTypicallyCanceledShortlyAfterBeingSet, maxSkewInMillisecondsDefault)
    {
    }

    public IOThreadTimer(Action<object> callback, object callbackState, bool isTypicallyCanceledShortlyAfterBeingSet, int maxSkewInMilliseconds)
    {
      this.callback = callback;
      this.callbackState = callbackState;
      this.maxSkew = Ticks.FromMilliseconds(maxSkewInMilliseconds);
      this.timerGroup =
          (isTypicallyCanceledShortlyAfterBeingSet ? TimerManager.Value.VolatileTimerGroup : TimerManager.Value.StableTimerGroup);
    }

    public static long SystemTimeResolutionTicks
    {
      get
      {
        if (IOThreadTimer.systemTimeResolutionTicks == -1)
        {
          IOThreadTimer.systemTimeResolutionTicks = GetSystemTimeResolution();
        }
        return IOThreadTimer.systemTimeResolutionTicks;
      }
    }

    [Fx.Tag.SecurityNote(Critical = "Calls critical method GetSystemTimeAdjustment", Safe = "method is a SafeNativeMethod")]
    [SecuritySafeCritical]
    static long GetSystemTimeResolution()
    {
      int dummyAdjustment;
      uint increment;
      uint dummyAdjustmentDisabled;

      if (UnsafeNativeMethods.GetSystemTimeAdjustment(out dummyAdjustment, out increment, out dummyAdjustmentDisabled) != 0)
      {
        return (long)increment;
      }

      // Assume the default, which is around 15 milliseconds.
      return 15 * TimeSpan.TicksPerMillisecond;
    }

    public bool Cancel()
    {
      return TimerManager.Value.Cancel(this);
    }

    public void Set(in TimeSpan timeFromNow)
    {
      if (timeFromNow != TimeSpan.MaxValue)
      {
        SetAt(Ticks.Add(Ticks.Now, Ticks.FromTimeSpan(timeFromNow)));
      }
    }

    public void Set(int millisecondsFromNow)
    {
      SetAt(Ticks.Add(Ticks.Now, Ticks.FromMilliseconds(millisecondsFromNow)));
    }

    public void SetAt(long dueTime)
    {
      TimerManager.Value.Set(this, dueTime);
    }

    [Fx.Tag.SynchronizationObject(Blocking = false, Scope = Fx.Tag.Strings.AppDomain)]
    class TimerManager
    {
      const long maxTimeToWaitForMoreTimers = 1000 * TimeSpan.TicksPerMillisecond;

      [Fx.Tag.Queue(typeof(IOThreadTimer), Scope = Fx.Tag.Strings.AppDomain, StaleElementsRemovedImmediately = true)]
      static TimerManager value = new TimerManager();

      Action<object> onWaitCallback;
      TimerGroup stableTimerGroup;
      TimerGroup volatileTimerGroup;
      [Fx.Tag.SynchronizationObject(Blocking = false)]
      WaitableTimer[] waitableTimers;

      bool waitScheduled;

      public TimerManager()
      {
        this.onWaitCallback = new Action<object>(OnWaitCallback);
        this.stableTimerGroup = new TimerGroup();
        this.volatileTimerGroup = new TimerGroup();
        this.waitableTimers = new WaitableTimer[] { this.stableTimerGroup.WaitableTimer, this.volatileTimerGroup.WaitableTimer };
      }

      object ThisLock
      {
        get { return this; }
      }

      public static TimerManager Value
      {
        get
        {
          return TimerManager.value;
        }
      }

      public TimerGroup StableTimerGroup
      {
        get
        {
          return this.stableTimerGroup;
        }
      }
      public TimerGroup VolatileTimerGroup
      {
        get
        {
          return this.volatileTimerGroup;
        }
      }

      public void Set(IOThreadTimer timer, long dueTime)
      {
        long timeDiff = dueTime - timer.dueTime;
        if (timeDiff < 0)
        {
          timeDiff = -timeDiff;
        }

        if (timeDiff > timer.maxSkew)
        {
          lock (ThisLock)
          {
            TimerGroup timerGroup = timer.timerGroup;
            TimerQueue timerQueue = timerGroup.TimerQueue;

            if (timer.index > 0)
            {
              if (timerQueue.UpdateTimer(timer, dueTime))
              {
                UpdateWaitableTimer(timerGroup);
              }
            }
            else
            {
              if (timerQueue.InsertTimer(timer, dueTime))
              {
                UpdateWaitableTimer(timerGroup);

                if (timerQueue.Count == 1)
                {
                  EnsureWaitScheduled();
                }
              }
            }
          }
        }
      }

      public bool Cancel(IOThreadTimer timer)
      {
        lock (ThisLock)
        {
          if (timer.index > 0)
          {
            TimerGroup timerGroup = timer.timerGroup;
            TimerQueue timerQueue = timerGroup.TimerQueue;

            timerQueue.DeleteTimer(timer);

            if (timerQueue.Count > 0)
            {
              UpdateWaitableTimer(timerGroup);
            }
            else
            {
              TimerGroup otherTimerGroup = GetOtherTimerGroup(timerGroup);
              if (otherTimerGroup.TimerQueue.Count == 0)
              {
                long now = Ticks.Now;
                long thisGroupRemainingTime = timerGroup.WaitableTimer.DueTime - now;
                long otherGroupRemainingTime = otherTimerGroup.WaitableTimer.DueTime - now;
                if (thisGroupRemainingTime > maxTimeToWaitForMoreTimers &&
                    otherGroupRemainingTime > maxTimeToWaitForMoreTimers)
                {
                  timerGroup.WaitableTimer.Set(Ticks.Add(now, maxTimeToWaitForMoreTimers));
                }
              }
            }

            return true;
          }
          else
          {
            return false;
          }
        }
      }

      void EnsureWaitScheduled()
      {
        if (!this.waitScheduled)
        {
          ScheduleWait();
        }
      }

      TimerGroup GetOtherTimerGroup(TimerGroup timerGroup)
      {
        if (object.ReferenceEquals(timerGroup, this.volatileTimerGroup))
        {
          return this.stableTimerGroup;
        }
        else
        {
          return this.volatileTimerGroup;
        }
      }

      void OnWaitCallback(object state)
      {
        WaitHandle.WaitAny(this.waitableTimers);
        long now = Ticks.Now;
        lock (ThisLock)
        {
          this.waitScheduled = false;
          ScheduleElapsedTimers(now);
          ReactivateWaitableTimers();
          ScheduleWaitIfAnyTimersLeft();
        }
      }

      void ReactivateWaitableTimers()
      {
        ReactivateWaitableTimer(this.stableTimerGroup);
        ReactivateWaitableTimer(this.volatileTimerGroup);
      }

      void ReactivateWaitableTimer(TimerGroup timerGroup)
      {
        TimerQueue timerQueue = timerGroup.TimerQueue;

        if (timerQueue.Count > 0)
        {
          timerGroup.WaitableTimer.Set(timerQueue.MinTimer.dueTime);
        }
        else
        {
          timerGroup.WaitableTimer.Set(long.MaxValue);
        }
      }

      void ScheduleElapsedTimers(long now)
      {
        ScheduleElapsedTimers(this.stableTimerGroup, now);
        ScheduleElapsedTimers(this.volatileTimerGroup, now);
      }

      void ScheduleElapsedTimers(TimerGroup timerGroup, long now)
      {
        TimerQueue timerQueue = timerGroup.TimerQueue;
        while (timerQueue.Count > 0)
        {
          IOThreadTimer timer = timerQueue.MinTimer;
          long timeDiff = timer.dueTime - now;
          if (timeDiff <= timer.maxSkew)
          {
            timerQueue.DeleteMinTimer();
            ActionItem.Schedule(timer.callback, timer.callbackState);
          }
          else
          {
            break;
          }
        }
      }

      void ScheduleWait()
      {
        ActionItem.Schedule(this.onWaitCallback, null);
        this.waitScheduled = true;
      }

      void ScheduleWaitIfAnyTimersLeft()
      {
        if (this.stableTimerGroup.TimerQueue.Count > 0 ||
            this.volatileTimerGroup.TimerQueue.Count > 0)
        {
          ScheduleWait();
        }
      }

      void UpdateWaitableTimer(TimerGroup timerGroup)
      {
        WaitableTimer waitableTimer = timerGroup.WaitableTimer;
        IOThreadTimer minTimer = timerGroup.TimerQueue.MinTimer;
        long timeDiff = waitableTimer.DueTime - minTimer.dueTime;
        if (timeDiff < 0)
        {
          timeDiff = -timeDiff;
        }
        if (timeDiff > minTimer.maxSkew)
        {
          waitableTimer.Set(minTimer.dueTime);
        }
      }
    }

    class TimerGroup
    {
      TimerQueue timerQueue;
      WaitableTimer waitableTimer;

      public TimerGroup()
      {
        this.waitableTimer = new WaitableTimer();
        this.waitableTimer.Set(long.MaxValue);
        this.timerQueue = new TimerQueue();
      }

      public TimerQueue TimerQueue
      {
        get
        {
          return this.timerQueue;
        }
      }
      public WaitableTimer WaitableTimer
      {
        get
        {
          return this.waitableTimer;
        }
      }
    }

    class TimerQueue
    {
      int count;
      IOThreadTimer[] timers;

      public TimerQueue()
      {
        this.timers = new IOThreadTimer[4];
      }

      public int Count
      {
        get { return count; }
      }

      public IOThreadTimer MinTimer
      {
        get
        {
          Fx.Assert(this.count > 0, "Should have at least one timer in our queue.");
          return timers[1];
        }
      }
      public void DeleteMinTimer()
      {
        IOThreadTimer minTimer = this.MinTimer;
        DeleteMinTimerCore();
        minTimer.index = 0;
        minTimer.dueTime = 0;
      }
      public void DeleteTimer(IOThreadTimer timer)
      {
        int index = timer.index;

        Fx.Assert(index > 0, "");
        Fx.Assert(index <= this.count, "");

        IOThreadTimer[] timers = this.timers;

        for (;;)
        {
          int parentIndex = index / 2;

          if (parentIndex >= 1)
          {
            IOThreadTimer parentTimer = timers[parentIndex];
            timers[index] = parentTimer;
            parentTimer.index = index;
          }
          else
          {
            break;
          }

          index = parentIndex;
        }

        timer.index = 0;
        timer.dueTime = 0;
        timers[1] = null;
        DeleteMinTimerCore();
      }

      public bool InsertTimer(IOThreadTimer timer, long dueTime)
      {
        Fx.Assert(timer.index == 0, "Timer should not have an index.");

        IOThreadTimer[] timers = this.timers;

        int index = this.count + 1;

        if (index == timers.Length)
        {
          timers = new IOThreadTimer[timers.Length * 2];
          Array.Copy(this.timers, timers, this.timers.Length);
          this.timers = timers;
        }

        this.count = index;

        if (index > 1)
        {
          for (;;)
          {
            int parentIndex = index / 2;

            if (parentIndex == 0)
            {
              break;
            }

            IOThreadTimer parent = timers[parentIndex];

            if (parent.dueTime > dueTime)
            {
              timers[index] = parent;
              parent.index = index;
              index = parentIndex;
            }
            else
            {
              break;
            }
          }
        }

        timers[index] = timer;
        timer.index = index;
        timer.dueTime = dueTime;
        return index == 1;
      }
      public bool UpdateTimer(IOThreadTimer timer, long dueTime)
      {
        int index = timer.index;

        IOThreadTimer[] timers = this.timers;
        int count = this.count;

        Fx.Assert(index > 0, "");
        Fx.Assert(index <= count, "");

        int parentIndex = index / 2;
        if (parentIndex == 0 ||
            timers[parentIndex].dueTime <= dueTime)
        {
          int leftChildIndex = index * 2;
          if (leftChildIndex > count ||
              timers[leftChildIndex].dueTime >= dueTime)
          {
            int rightChildIndex = leftChildIndex + 1;
            if (rightChildIndex > count ||
                timers[rightChildIndex].dueTime >= dueTime)
            {
              timer.dueTime = dueTime;
              return index == 1;
            }
          }
        }

        DeleteTimer(timer);
        InsertTimer(timer, dueTime);
        return true;
      }

      void DeleteMinTimerCore()
      {
        int count = this.count;

        if (count == 1)
        {
          this.count = 0;
          this.timers[1] = null;
        }
        else
        {
          IOThreadTimer[] timers = this.timers;
          IOThreadTimer lastTimer = timers[count];
          this.count = --count;

          int index = 1;
          for (;;)
          {
            int leftChildIndex = index * 2;

            if (leftChildIndex > count)
            {
              break;
            }

            int childIndex;
            IOThreadTimer child;

            if (leftChildIndex < count)
            {
              IOThreadTimer leftChild = timers[leftChildIndex];
              int rightChildIndex = leftChildIndex + 1;
              IOThreadTimer rightChild = timers[rightChildIndex];

              if (rightChild.dueTime < leftChild.dueTime)
              {
                child = rightChild;
                childIndex = rightChildIndex;
              }
              else
              {
                child = leftChild;
                childIndex = leftChildIndex;
              }
            }
            else
            {
              childIndex = leftChildIndex;
              child = timers[childIndex];
            }

            if (lastTimer.dueTime > child.dueTime)
            {
              timers[index] = child;
              child.index = index;
            }
            else
            {
              break;
            }

            index = childIndex;

            if (leftChildIndex >= count)
            {
              break;
            }
          }

          timers[index] = lastTimer;
          lastTimer.index = index;
          timers[count + 1] = null;
        }
      }
    }

    [Fx.Tag.SynchronizationPrimitive(Fx.Tag.BlocksUsing.NonBlocking)]
    class WaitableTimer : WaitHandle
    {

      long dueTime;

      [Fx.Tag.SecurityNote(Critical = "Call the critical CreateWaitableTimer method in TimerHelper",
          Safe = "Doesn't leak information or resources")]
      [SecuritySafeCritical]
      public WaitableTimer()
      {
        this.SafeWaitHandle = TimerHelper.CreateWaitableTimer();
      }

      public long DueTime
      {
        get { return this.dueTime; }
      }

      [Fx.Tag.SecurityNote(Critical = "Call the critical Set method in TimerHelper",
          Safe = "Doesn't leak information or resources")]
      [SecuritySafeCritical]
      public void Set(long dueTime)
      {
        this.dueTime = TimerHelper.Set(this.SafeWaitHandle, dueTime);
      }
      [Fx.Tag.SecurityNote(Critical = "Provides a set of unsafe methods used to work with the WaitableTimer")]
      [SecurityCritical]
      static class TimerHelper
      {
        public static unsafe SafeWaitHandle CreateWaitableTimer()
        {
          SafeWaitHandle handle = UnsafeNativeMethods.CreateWaitableTimer(IntPtr.Zero, false, null);
          if (handle.IsInvalid)
          {
            Exception exception = new Win32Exception();
            handle.SetHandleAsInvalid();
            throw Fx.Exception.AsError(exception);
          }
          return handle;
        }
        public static unsafe long Set(SafeWaitHandle timer, long dueTime)
        {
          if (!UnsafeNativeMethods.SetWaitableTimer(timer, ref dueTime, 0, IntPtr.Zero, IntPtr.Zero, false))
          {
            throw Fx.Exception.AsError(new Win32Exception());
          }
          return dueTime;
        }
      }
    }
  }
}
#endif
